#include <stdio.h>
#include <stdlib.h>

typedef struct QNode
{
    int data;
    struct QNode *next;
} QNode, *QueuePtr;

typedef struct
{
    QueuePtr front;
    QueuePtr rear;
} LinkQueue;

bool InitQueue(LinkQueue &Q);       // 初始化
bool DestoryQueue(LinkQueue &Q);    // 销毁
bool ClearQueue(LinkQueue &Q);      // 清空
bool QueueEmpty(LinkQueue Q);       // 判空
int QueueLength(LinkQueue Q);       // 长度
bool GetHead(LinkQueue Q, int &e);  // 队首
bool EnQueue(LinkQueue &Q, int &e); // 入队
bool DeQueue(LinkQueue &Q, int &e); // 出队

// 初始化
bool InitQueue(LinkQueue &Q)
{
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if (!Q.front)
        return false;
    Q.front->next = NULL;
    return true;
}
bool DestoryQueue(LinkQueue &Q)
{
    while (Q.front)
    {
        Q.rear = Q.front->next;
        free(Q.front);
        Q.front = Q.rear;
    }
    return true;
}
bool ClearQueue(LinkQueue &Q)
{
    return true;
}
bool QueueEmpty(LinkQueue Q)
{
    return true;
}
int QueueLength(LinkQueue Q)
{
    return 0;
}
bool GetHead(LinkQueue Q, int &e)
{
    if (Q.front == Q.rear)
        return false;
    e = Q.front->next->data;
    return true;
}
bool EnQueue(LinkQueue &Q, int e)
{
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    if (!p)
        return false;
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
    return true;
}
bool DeQueue(LinkQueue &Q, int &e)
{
    if (Q.front == Q.rear)
        return false;
    QueuePtr p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if (Q.rear == p)
        Q.rear = Q.front;
    free(p);
    return true;
}
void Print(LinkQueue Q)
{
    printf("\n-----队首-----\n");
    QNode *p = Q.front;
    while (p != Q.rear)
    {
        printf("%d \n", p->next->data);
        p = p->next;
    }
    printf("-----队尾-----\n\n");
}
int main()
{
    // 初始化
    LinkQueue Q;
    InitQueue(Q);

    // 入队
    EnQueue(Q, 5);
    EnQueue(Q, 6);
    EnQueue(Q, 2);
    EnQueue(Q, 9);
    EnQueue(Q, 1);
    EnQueue(Q, 3);
    Print(Q);

    // 队首
    int e;
    GetHead(Q, e);
    printf("队首元素为%d \n", e);

    // 出队
    DeQueue(Q, e);
    printf("队首元素%d 出栈\n", e);
    Print(Q);
}